// hdu5377
// run: $exec < input
#include <cstdio>
#include <cmath>

typedef long long value_type;
value_type a, b, p; // a ^ x == b (mod p)
value_type sum, m;

namespace hash
{
	int const maxlen = 1299721;
	int hashed[maxlen];
	value_type key[maxlen];
	int value[maxlen];
	int timestamp = 1;

	void init() { timestamp++; }

	void insert(value_type k, int v)
	{
		int i = k % maxlen;
		for (; hashed[i] == timestamp && key[i] != k; i = (i + 1) % maxlen);
		if (hashed[i] != timestamp) { hashed[i] = true; key[i] = k; value[i] = v; }
	}

	int find(value_type k)
	{
		value_type i = k % maxlen;
		for (; hashed[i] == timestamp && key[i] != k; i = (i + 1) % maxlen);
		if (hashed[i] != timestamp) return -1;
		return value[i];
	}
};

value_type euler_totient(int x) // this case x is a prime
{
	return x - 1;
}

void extended_gcd(value_type a,  value_type b, value_type & d, value_type & x, value_type & y)
{
	if (!b) { d = a; x = 1; y = 0; }
	else {
		extended_gcd(b, a % b, d, y, x);
		y -= x * (a/b);
	}
}

// univariate_modular_system_of_linear_equation
value_type umsole(value_type a, value_type b, value_type p)
{
	// a*x  is congruent to  b  modulo  p
	// => a*x + p*(-y) = b
	value_type x, y, b0;
	extended_gcd(a, p, b0, x, y);
	value_type m = p / b0;
	return ((x * (b / b0)) % m + m) % m;
}

value_type baby_step_giant_step(value_type a, value_type b, value_type p)
{
	value_type m = std::ceil(std::sqrt((double)euler_totient(p)));
	hash::init();
	value_type d = 1;
	for (int i = 0; i < m; i++) {
		hash::insert(d, i);
		d = (d * a) % p;
	}

	// now d = a^m
	value_type di = 1; // d^i
	for (int i = 0; i < m; i++) {
		value_type x = umsole(di, b, p);
		int tmp  = hash::find(x);
		if (tmp != -1)
			return i * m + tmp;
		di = (di * d) % p;
	}
	return -1;
}

int main()
{
	int T; std::scanf("%d", &T);
	for (int ti = 1; ti <= T; ti++) {
		std::scanf("%lld %lld", &sum, &m);
		for (int i = 0; i < m; i++) {
			while (std::scanf("%lld %lld %lld", &p, &a, &b) != EOF) {
				value_type ans = baby_step_giant_step(a, b, p);
				if (ans == -1) std::printf("no solution\n");
				else		   std::printf("%lld\n", ans);
			}
		}
	}
}

